/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年04月25日
*   描    述：
*
================================================================*/

#include <stdio.h>

struct ListNode {
  int val;
  struct ListNode* next;
};

struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
  // 根据listSize大小将现有的lists分为两组，lists1和lists2。

  // 递归进行上面的操作，直到listsSize等于2或者等于1，等于2的时候进行归并操作，等于1的时候直接返回这唯一的list。
}

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
  int val;
  struct ListNode* next;
};

// 合并两个有序链表
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
  if (l1 == NULL) return l2;
  if (l2 == NULL) return l1;

  struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
  dummy->next = NULL;
  struct ListNode* tail = dummy;

  while (l1 && l2) {
    if (l1->val <= l2->val) {
      tail->next = l1;
      l1 = l1->next;
    } else {
      tail->next = l2;
      l2 = l2->next;
    }
    tail = tail->next;
  }

  if (l1) tail->next = l1;
  if (l2) tail->next = l2;

  struct ListNode* mergedList = dummy->next;
  free(dummy);
  return mergedList;
}

// 递归合并 k 个有序链表
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize) {
  if (listsSize == 0) return NULL;
  if (listsSize == 1) return lists[0];

  int mid = listsSize / 2;
  struct ListNode* left = mergeKLists(lists, mid);
  struct ListNode* right = mergeKLists(lists + mid, listsSize - mid);

  return mergeTwoLists(left, right);
}

// 创建链表节点
struct ListNode* createNode(int val) {
  struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
  newNode->val = val;
  newNode->next = NULL;
  return newNode;
}

// 在链表尾部添加节点
void append(struct ListNode** head, int val) {
  if (*head == NULL) {
    *head = createNode(val);
    return;
  }

  struct ListNode* newNode = createNode(val);
  struct ListNode* current = *head;

  while (current->next != NULL) {
    current = current->next;
  }

  current->next = newNode;
}

int main() {
  // 创建示例链表
  struct ListNode* lists[3] = {NULL};
  append(&lists[0], 1);
  append(&lists[0], 4);
  append(&lists[0], 5);

  append(&lists[1], 1);
  append(&lists[1], 3);
  append(&lists[1], 4);

  append(&lists[2], 2);
  append(&lists[2], 6);

  struct ListNode* mergedList = mergeKLists(lists, 3);

  return 0;
}
